package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;
import java.util.Arrays;

/**
 * @author：zzc
 * @date: 2022/9/4
 */
public class 排序之快排 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 5, 6, 3, 2, 4, 6, 2, 6, 7, 78, 4, 5, 45, 2, 3, 42, 4, 1, 24, 2, 6, 4, 57, 45, 2345};
        System.out.println(Arrays.toString(StopWatchTemplate.doSupplier(() -> quickSort2(nums, 0, nums.length - 1))));
    }

    private static int[] quickSort2(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) {
            return null;
        }
        // 生成 分区指示器
        int zoneIndex = partition(array, start, end);
        if(zoneIndex>start)
            quickSort2(array,start,zoneIndex-1);
        if(zoneIndex<end)
            quickSort2(array,zoneIndex+1,end);

        return array;
    }

    // 生成分区指示器  将数据分成两部分时 从哪分区的指示器 快速排序分区方法
    private static int partition(int[] array, int start, int end) {
        if(start==end) return start;
        //随机选取一个基准数
        int pivot = (int) (start+Math.random()*(end-start+1));
        // zoneIndex是分区指示器 初始值为分区头元素下标-1
        int zoneIndex = start-1;

        // 将基准数和分区尾元素交换位置
        swap(array,pivot,end);
        for (int i = start; i <=end; i++) {
           //当前元素小于等于基准数
            if (array[i] <= array[end]) {
                // 首先分区指示器++
                zoneIndex++;
                // 当前元素在分区指示器的右边时 交换当前元素和分区指示器元素
                if(i>zoneIndex)
                    swap(array,i,zoneIndex);
            }
        }
        return zoneIndex;
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    /**
     * a -- 待排序的数组
     * l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     * r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    private static String quickSort(int[] a, int l, int r) {

        if (l < r) {
            int i, j, x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while (i < j && a[j] > x) {
                    j--; // 从右向左找第一个小于x的数
                }
                if (i < j) {
                    a[i++] = a[j];
                }
                while (i < j && a[i] < x) {
                    i++; // 从左向右找第一个大于x的数
                }
                if (i < j) {
                    a[j--] = a[i];
                }
            }
            a[i] = x;
            quickSort(a, l, i - 1); /* 递归调用 */
            quickSort(a, i + 1, r); /* 递归调用 */
        }

        return Arrays.toString(a);
    }


}
